#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/core/stack.h>
#include "control.h"

using namespace leda;

void display_node_markers(GraphWin &gw , node &v , node_array<int> pre , node_array<int> low) {
	string label = "pre: " + string("%i" , pre[v]) + " \nlow: " + string("%i" , low[v]);
	gw.set_user_label(v , label);
}

//Color a block in specified color, color articulation node red
void color_block(graph &g , GraphWin &gw , edge &e , stack<edge> &edge_stack , int &color , node_array<bool> &articulation_marker) {
	//let user know that we found a block and are coloring it right now
	gw.message("We found a block. Next we pop edges and color them.");

	//pop edges until e is reached and color them in specified color
	while (edge_stack.top() != e){
		edge current_edge = edge_stack.pop();
		node target = g.target(current_edge);
		node source = g.source(current_edge);

		gw.set_color(current_edge, color);

		//ignore articulation nodes since they stay red
		if (!articulation_marker[source])
			gw.set_color(source , color);
		if (!articulation_marker[target])
			gw.set_color(target , color);
		control_wait(1);
	}
	gw.set_color(edge_stack.pop(), color);

	gw.redraw();
	gw.del_message();
}

//Marks an articulation node and colors it
void mark_artuculation_node(node v, node_array<bool>& articulation_marker,
		GraphWin& gw) {
	//remember articulation vertices
	articulation_marker[v] = true;
	//mark articulation vertice red
	gw.set_color(v, red);
}

void blocksBiconnectivity(node parent, node v, graph &g, GraphWin &gw, node_array<int> &pre,
		node_array<int> &low, node_array<int> &nr_children, int &akt, stack<edge> &edge_stack, int &color,
		node_array<bool> &articulation_marker) {

	//labels get too big to be displayed inside a node, therefore we display them next to it.
	gw.set_label_pos(v , east_pos);

    edge e;

	pre[v] = akt++;
    low[v] = pre[v];

    display_node_markers(gw , v , pre , low);
    gw.set_color(v, green);
    gw.redraw();
    control_wait(0.5);

    forall_inout_edges(e, v)
    {
        node w = g.opposite(v, e);
        // we ignore edges pointing back to parent
        if (w != parent)
        {
        	// if node has not been visited yet
            if (pre[w] < 0)
            {
            	nr_children[v]++;
                gw.set_color(e, green);
                edge_stack.push(e);
                control_wait(0.5);

                blocksBiconnectivity(v, w, g, gw, pre, low, nr_children, akt, edge_stack, color, articulation_marker);
                //backtracking, mark edge as done
                gw.set_color(e, red);
                gw.set_color(w, red);
                control_wait(0.5);

                //update low value and the according label
                low[v] = min(low[v], low[w]);
                display_node_markers(gw , v , pre , low);

                // if it has more than two children then it is an articulation vertice
                if (pre[v] == 0 && nr_children[v] >= 2){
					mark_artuculation_node(v, articulation_marker, gw);

                	// pop the saved edges in the stack, color them, color articulation vertice
                	color_block(g , gw , e , edge_stack , color , articulation_marker);
                	color++; //change the color, so there are different colored edges in different blocks
                	continue; //skip next if block
                }

                //New Block found
                if ((low[w] >= pre[v])) {
                	//if this is the starting node it is not an articulation node
                	if (pre[v] != 0)
						mark_artuculation_node(v, articulation_marker, gw);

                	// pop the saved edges in the stack, color them, color articulation vertice
                	color_block(g , gw , e , edge_stack , color , articulation_marker);
                	color++; //change the color, so there are different colored edges in different blocks
                }
            }
            // if node has been visited already
            else
            {
                if (pre[w] < pre[v])
                {
                	low[v] = min(low[v], pre[w]);
                    display_node_markers(gw , v , pre , low);

                	// e is a back edge, still we color it green so we know in which point the dfs is
                    edge_stack.push(e);
                    gw.set_style(e , dotted_edge);
                    gw.set_color(e, green);
                    control_wait(0.5);
                }
            }
        }
    }
}


int main(int argc, char *argv[]) {

    GraphWin gw(800, 600);
    gw.display();
    create_control();
    gw.set_directed(false);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close(); destroy_control();
        exit(1);
    }

    // preorder numbers, initialized to -1
    node_array<int> pre(g, -1);

    // minimal preorder numbers
    node_array<int> low(g, -1);

    // number of children of the node
    node_array<int> nr_children(g, 0);

    // articulation node marker
    node_array<bool> articulation_marker(g,false);

    // current visited node value
    int akt = 0;

    // stack with the edges from a block
    stack<edge> edge_stack;

    // color in integer
    int color = 6;

    // initialize graph nodes and edges as grey3
    node v;
    edge e;
    forall_nodes(v, g) {
        gw.set_label_type(v, user_label);
        gw.set_color(v, grey3);
    }
    forall_edges(e, g){
    	gw.set_width(e, 3);
        gw.set_color(e, grey3);
    }
    // read starting node
    while ((v = gw.read_node()) == NULL) ;

    // start algorithm
    // repeat until akt reaches the number of nodes
    do {

    	blocksBiconnectivity(v, v, g, gw, pre, low, nr_children, akt, edge_stack, color , articulation_marker);

    } while (akt < g.number_of_nodes());

    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
